#ifndef __ConjString_H__
#define __ConjString_H__

#include <iostream>
#include <string>
#include <cassert>

using namespace std;

/*****************************************************
Conjunto. Aclaraciones Generales: la clase ConjString
no busca implementar la idea de un conjunto parametrizado 
sino la de un conjunto de strings formados por caracteres 
alfabéticos en minúscula. La funcionalidad se garantiza 
únicamente para este tipo de strings. No se asegura
el funcionamiento para strings que incluyan caracteres 
de otro tipo (mayúsculas, números, símbolos), si bien
se podría aumentar el alfabeto con cambios mínimos en
la estructura interna del conjunto. 
Utilizamos la librería estándar de strings. Eso significa
cambios mínimos sobre la fase de diseño. En aquella 
hacíamos una copia del string y la iterábamos pidiéndo
el primer elemento y quedándonos con el fin. En este caso
manejamos la iteración con un entero como índice.
*******************************************************/

// Definición de estructuras auxiliares
struct NodoConjString {
	string elemento;
	NodoConjString *siguiente;
};

struct NodoTrie {
	NodoTrie* hijos[27];
	bool fin;
};

// Definición de la clase
class ConjString
{
	friend class IteradorConjString;
	friend class ConjStringTest;
	public:
		// el constructor crea el ConjString vacio
		ConjString();
		// crea un ConjString como copia de otro. 
		ConjString(const ConjString &otro);
		// Destructor
		~ConjString();
		// agrega un string al conjunto
		void agregar(const string &s);
		// elimina un string del conjunto
		void eliminar(const string &s);

		bool pertenece(const string &s) const;

		int dameTamano() const;

		bool vacio() const;

		// asignación por copia de un conjunto
		ConjString &operator=(const ConjString &otro); 

		// Imprime el ConjString en pantalla en forma legible.

		friend ostream & operator<<(ostream &o, const ConjString &esp);
	private:
		int tamano;
		NodoConjString *listaEnlazada;
		NodoTrie *trie;
		
};

// Iterador
class IteradorConjString {
	public:
		IteradorConjString();
		IteradorConjString(const ConjString &c);
		string proximo();
		bool tieneProximo() const;
		IteradorConjString &operator=(const IteradorConjString &otra);
	private:
		NodoConjString *lista;
};


// funciones auxiliares
int char2nat( char ch ) {
	return ch - 97;
}
// funciones auxiliares para el manejo de memoria
bool hayMasRamas (const NodoTrie &n, int i) {
	int i2 = 0;
	bool retorno = false;
	while (i2 < 27 && !retorno) {
		if (i2 != i)
			retorno = (n.hijos[i2] != NULL);
		i2++;
	}
	return retorno;
}

bool esUnaHoja(const NodoTrie &n) {
	int i = 0;
	bool retorno = true;
	while ( i < 27 && retorno) {
		if (n.hijos[i] != NULL) {
			retorno = false;
		}
		i++;
	}
	return retorno;
}

void borrarRama(NodoTrie ** &n) {
	NodoTrie *aux;
	aux = *n;
	int i = 0;
	while (i != 27) {
		i = 0;
		while ((*n) -> hijos[i] == NULL && i != 27) {
			i++;
		}
		if (i != 27) {
			*n = (*n) -> hijos[i];
			delete aux;
			aux = *n;
		}
	}
	aux = *n;
	delete aux;
	*n = NULL;
}

// Implementación de las funciones

ConjString::ConjString() {
	tamano = 0;
	listaEnlazada = NULL;
	trie = NULL;
}

ConjString::~ConjString() {
	NodoConjString *p;
	string aux;
	p = listaEnlazada;
	while ( ! (p == NULL) ) {
		aux = p -> elemento;
		p = (p -> siguiente);
		eliminar(aux);
	}
}

ConjString::ConjString(const ConjString &otro) {
	tamano = 0;
	listaEnlazada = NULL;
	trie = NULL;
	NodoConjString *p;
	string aux;
	p = otro.listaEnlazada;
	while ( ! (p == NULL) ) {
		aux = p -> elemento;
		p = (p -> siguiente);
		agregar(aux);
	}
}

bool ConjString::vacio() const {
	return (listaEnlazada == NULL);
}

int ConjString::dameTamano() const{
	return tamano;
}

bool ConjString::pertenece(const string &s) const {

	NodoTrie *p;
	bool retorno;
	p = trie;
	retorno = true;
	int i = 0;
	
	if ( p == NULL ) 
		retorno = false; // si el trie es nulo devuelve falso para cualquier elemento
	else {
		while (i < s.length() && retorno)  /* va a bajar en el trie hasta agotar el String */ {
			if (p -> hijos[char2nat(s[i])] == NULL ) {
				retorno = false; // si no puede seguir devuelve false
			}
			else 
				p = p -> hijos[char2nat(s[i])];
			i++;			
		}		
		if (retorno)
		retorno = p -> fin;
	}
	return retorno;
}

void ConjString::agregar(const string &s) {
	NodoTrie *p;
	int i;
	int j= 0;
	NodoConjString *p_nuevoNodo;
	if (trie == NULL) {
		trie = new NodoTrie();
		i = 0;
		while ( i < 27) {
			trie-> hijos[i] = NULL;
			i++;
		}
	}
	p = trie;
	while (j < s.length()) {
		i = 0;
		if( p -> hijos[char2nat(s[j])] == NULL ) {
			p -> hijos[char2nat(s[j])] = new NodoTrie();
			while ( i < 27) {
				(p -> hijos[char2nat(s[j])]) -> hijos[i] = NULL;
				i++;
			}			
			p -> hijos[char2nat(s[j])] -> fin = false;
		}
		p = p -> hijos[char2nat(s[j])];
		j++;
	}
	if ( p -> fin == false ) { // si no estaba ya el elemento en el conjunto 
		tamano++;
		p -> fin = true;
		// se agrega el elemento en la lista enlazada
		p_nuevoNodo = new NodoConjString();
		p_nuevoNodo -> elemento = s;
		p_nuevoNodo -> siguiente = listaEnlazada;
		listaEnlazada = p_nuevoNodo;
	}
}

void ConjString::eliminar(const string &s) {
	NodoConjString * i1;
	NodoConjString ** i2;
	bool encontrado, aux;
	NodoTrie *p, **p1;
	int i = 0;
	char proxAux, proximo;
	p = trie;
	encontrado = false;
	p1 = &trie;
	while ((i < s.length()) && (p != NULL)) {
		proxAux = s[i];
		/*	Si de este nodo que estoy considerando se desprenden más ramas que aquélla en la que se encontraría el elemento a borrar o bien 
			termina un elemento que se encuentra en el conjunto y no llegué al final del String, guardo el nodo en p1, ya que a partir de aquí
			tendré que borrar los nodos, de ser una rama de ahora en más hasta el ultimo caracter del String.
		*/
		i++;
		if ( p -> fin | hayMasRamas(*p, char2nat(proxAux)) ) {
			p1 = &(p -> hijos[char2nat(proxAux)]);
			proximo = proxAux;
		}
		p = p -> hijos[char2nat(proxAux)];	
	}
	if (p != NULL) 	{
		if ((p -> fin) && i <= s.length()) 
			encontrado = true;
	}
	// si encontramos el elemento lo eliminamos de la lista y del trie
	if (encontrado)	{
		// eliminamos el elemento de la lista
		i1 = listaEnlazada;
		i2 = &listaEnlazada;
		encontrado = false;
		while (!encontrado) {
			if ( i1 -> elemento == s) { // si encuentra el elemento
				encontrado = true;
				tamano--;
				*i2 = i1 -> siguiente;
				delete i1;
			}
			else {
				i2 = &(i1 -> siguiente);
				i1 = i1 -> siguiente;
			}
		}
		// eliminamos el elemento del trie
		if (esUnaHoja (*p)) {
			borrarRama(p1);
		}else {
			(p -> fin) = false;	
		}
	}	
}

ConjString & ConjString::operator=(const ConjString &otro) {
	if (this != &otro) {
		NodoConjString *p;
		string aux;
		p = listaEnlazada;
		while ( ! (p == NULL) ) {
			aux = p -> elemento;
			p = (p -> siguiente);
			eliminar(aux);

		}
		p = otro.listaEnlazada;
		while ( ! (p == NULL) ) {
			aux = p -> elemento;
			p = (p -> siguiente);
			agregar(aux);

		}
		
	}	
	return *this;
}


// funciones de iteradores

IteradorConjString::IteradorConjString() {
	lista = NULL;
}

IteradorConjString::IteradorConjString(const ConjString &c) {
	lista = c.listaEnlazada;
}

string IteradorConjString::proximo() {
	string aux = lista -> elemento;
	lista = lista -> siguiente;
	return aux;
}

bool IteradorConjString::tieneProximo() const {
	return (lista != NULL);
}

ostream &operator<<(ostream &o, const ConjString &esp){
	IteradorConjString it(esp);
	while (it.tieneProximo()) {
		o << it.proximo() << endl;
	}
	return o;
}

IteradorConjString& IteradorConjString::operator=(const IteradorConjString &otra) {
	if (this != &otra) 
		lista = otra.lista;
	return *this;
}

#endif 
